package exerise;

/**
 * 最长回文子串
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 * <p>
 * 示例 1：
 * <p>
 * 输入: "babad"
 * 输出: "bab"
 * 注意: "aba" 也是一个有效答案。
 * 示例 2：
 * <p>
 * 输入: "cbbd"
 * 输出: "bb"
 */
public class Ex5 {

    public static void main(String[] args) {
        String src = "mabakabak";
//        String src = "acbbcbds";
//        String src = "cbc";
        Ex5 ex5 = new Ex5();
        String result1 = ex5.longestPalindrome1(src);
        System.out.println("result1 == " + result1);

        String result2 = ex5.longestPalindrome2(src);
        System.out.println("result2 == " + result2);

        String result3 = ex5.longestPalindrome3(src);
        System.out.println("result3 == " + result3);

        String result4 = ex5.longestPalindrome4(src);
        System.out.println("result4 == " + result4);
    }

    //暴力法 O(n^3) O(1)
    public String longestPalindrome1(String s) {
        String ans = "";
        for (int i = 0; i < s.length(); i++) { // start
            for (int j = i; j < s.length(); j++) { //end
                String temp = s.substring(i, j + 1);
                int count = 0;
                for (int k = 0; k < temp.length() / 2; k++) {
                    if (temp.charAt(k) == temp.charAt(temp.length() - 1 - k)) {
                        count++;
                    }
                }
                if (count == temp.length() / 2 && temp.length() >= ans.length()) {
                    ans = temp;
                }
            }
        }
        return ans;
    }

    //动态规划 O(n^2) O(n^2)
    public String longestPalindrome2(String s) {
        int n = s.length();
        boolean[][] d = new boolean[n][n];
        int left = 0, right = 0;
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                d[i][i] = true;
                d[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || d[i + 1][j - 1]);
                if (d[i][j] && right - left < j - i) {
                    left = i;
                    right = j;
                }
            }
        }
        return s.substring(left, right + 1);
    }

    //中心法 O(n^2) O(1)
    public String longestPalindrome3(String s) {
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandCenter(s, i, i);
            int len2 = expandCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private int expandCenter(String s, int start, int end) {
        int left = start, right = end;
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }

    //Manacher算法 O(n) O(1)
    public String longestPalindrome4(String s) {
        if (s == null || s.length() < 1) {
            return s;
        }
        String newStr = manacherStr(s);
        int c = -1;
        int r = -1;
        int n = newStr.length();
        int[] p = new int[n];
        int pMax = 0;
        int iMax = 0;
        for (int i = 0; i < n; i++) {
            if (i > r) {  //i > r
                c = i;
                int j = 1;
                while (i - j >= 0 && i + j < n && newStr.charAt(i - j) == newStr.charAt(i + j)) { //bound
                    j++;
                }
                p[i] = j;
                r = c + j - 1;
            } else { // i <= r
                int p2 = 2 * c - i; // i symmetry point
                int rL = 2 * c - r; //right symmetry point
                int pL = p2 - p[p2] + 1;    // p2 symmetry point left
                if (rL < pL) {
                    p[i] = p[p2];
                } else if (rL > pL) {
                    p[i] = r - i + 1;
                } else {
                    c = i;
                    int j = r - i + 1;
                    while (i - j >= 0 && i + j < n && newStr.charAt(i - j) == newStr.charAt(i + j)) { //bound
                        j++;
                    }
                    p[i] = j;
                    r = c + j - 1;
                }
            }
            //record index , max radius
            if (p[i] > pMax) {
                pMax = p[i];
                iMax = i;
            }
        }

        int start = iMax - pMax + 1;
        int end = iMax + pMax;
        String temp = newStr.substring(start, end);
        return originStr(temp);
    }

    public String manacherStr(String s) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            builder.append("#");
            builder.append(s.charAt(i));
        }
        builder.append("#");
        return builder.toString();
    }

    public String originStr(String s) {
        return s.replaceAll("#", "");
    }

}
